template <typename Comparable>
 class BinarySearchTree
 {
 
 private:
 struct BinaryNode
 {
 Comparable element;
 BinaryNode *left;
 BinaryNode *right;
int count;

 BinaryNode( const Comparable & theElement, const int &_count ,BinaryNode *lt, BinaryNode *rt )
 : element{ theElement }, left{ lt }, right{ rt }, count{_count}{ } 

 BinaryNode( Comparable && theElement, const int &_count,BinaryNode *lt, BinaryNode *rt )
 : element{ std::move( theElement ) }, left{ lt }, right{ rt },count{_count} { }
 };

 BinaryNode *root;
 public:
 
 BinarySearchTree( ){
 root=nullptr;
 }

 void makeEmpty( BinaryNode * & t )
 {
 if( t != nullptr )
 {
 makeEmpty( t->left );
 makeEmpty( t->right );
 
delete t;
 }
 t = nullptr;
 }

 
~BinarySearchTree( )
 {
 makeEmpty( root);
 }
 
 
 
 void insert( const Comparable & x, BinaryNode *&t)
 {
 if( t == nullptr )
 t = new BinaryNode{ x,1, nullptr, nullptr };
 else if( x < t->element )
 insert( x, t->left );
 else if( t->element < x )
 insert( x, t->right );
 else t->count++;
}

 void insert( const Comparable & x )
 {
 insert( x, root );
 }
 void insert( Comparable && x, BinaryNode *&t)
 {
 if( t == nullptr )
 t = new BinaryNode{ std::move( x ), 1,nullptr, nullptr };
 else if( x < t->element )
 insert( std::move( x ), t->left );
 else if( t->element < x )
 insert( std::move( x ), t->right );
 else t->count++;
    }
 void insert( Comparable && x)
 {
 insert( x, root );
 }
 void printTree(std::vector<Comparable> &_data,BinaryNode *t ){
 if (t==nullptr) return; 
 printTree(_data,t->left);
 for(int i=0;i<t->count;i++){
    _data.push_back(t->element);
 }
 printTree(_data,t->right);
 } 
 void printTree(std::vector<Comparable> &_data){
     printTree(_data,root);
 }
 };
 
 template<class T>
 void BST_sort(std::vector<T> &_data){
     BinarySearchTree <T> t;
   for(int i=0;i<_data.size();i++){
       t.insert(_data[i]);
   }
   _data.clear();
   t.printTree(_data);
 }

template<class T>
void Randomized_BST_sort(std::vector<T> &_data){
    random_shuffle(_data.begin(),_data.end());
    BST_sort(_data);
}
